1. Field of the Invention
The present invention generally relates to an algorithm for the synchronization of clocks in address independent networks including, but not limited to, token rings and token busses and, more particularly, to an algorithm which takes advantage of characteristics of the network by using the fastest clock in the network as the master.
2. Description of the Prior Art
In a distributed computer system, if shared resources are accessed, a log of the sequence of accesses must be maintained so that in the event of a failure, transactions can be restarted in the correct order. As transactions are ordered in a log via a time stamp, all the clocks in the system must be synchronized closely enough so as to ensure the consistency of the log. Such clocks are sometimes referred to as "real-time" clocks.
A number of algorithms that place no restriction on the topology of the network or the kind of routing employed have been proposed. See, for example, Cristian, F., H. Aghili and R. Strong, "Clock Synchronization in the Presence of Omission and Performance Faults and Processor Joins", Proc. of the 16th Intnl. Symposium on Fault Tolerant Computing, Vienna, June 1986, Dolev, D., J. Halpern, B. Simons and R. Strong, "Fault Tolerant Clock Synchronization", Proceedings of the 3rd Annual ACM Symposium on Principles of Distributed Computing, 1984, pp. 89-102, Lamport, L., and M. Melliar-Smith, "Synchronizing Clocks in the Presence of Faults", Journal of the ACM, vol. 32, No. 1, Jan. 1985, pp. 52-78, and Lundelius, J., and N. Lynch, "A New Fault Tolerant Algorithm for Clock Synchronization", Proc. 3rd ACM Symposium on the Principles of Distributed Computing, 1983.
Messages containing local clock times are passed between processors until all the clocks in the network are synchronized to within some quantity .DELTA.. To prevent messages persisting indefinitely in the network, each time a clock synchronization message is received at a node, it is processed and a decision is made as to whether or not an outgoing message is to be generated. Notice that this requires the clock synchronization message to be brought up into and processed by the system software. As software delays are typically an order of magnitude greater than link delays, this limits the accuracy with which the clocks can be synchronized. In addition, the algorithms employed tend to be complex.